TNotes.leetcode

Appearance

1021. 删除最外层的括号【简单】

1021. 删除最外层的括号【简单】 ​

1. 📝 题目描述 ​

有效括号字符串为空 ""、"(" + A + ")" 或 A + B，其中 A 和 B 都是有效的括号字符串，+ 代表字符串的连接。

  • 例如，""，"()"，"(())()" 和 "(()(()))" 都是有效的括号字符串。

如果有效字符串 s 非空，且不存在将其拆分为 s = A + B 的方法，我们称其为原语（primitive），其中 A 和 B 都是非空有效括号字符串。

给出一个非空有效字符串 s，考虑将其进行原语化分解，使得：s = P_1 + P_2 + ... + P_k，其中 P_i 是有效括号字符串原语。

对 s 进行原语化分解，删除分解中每个原语字符串的最外层括号，返回 s。

示例 1：

txt
输入：s = "(()())(())"
输出："()()()"

解释：
输入字符串为 "(()())(())"，原语化分解得到 "(()())" + "(())"，
删除每个部分中的最外层括号后得到 "()()" + "()" = "()()()"。

示例 2：

txt
输入：s = "(()())(())(()(()))"
输出："()()()()(())"

解释：
输入字符串为 "(()())(())(()(()))"，原语化分解得到 "(()())" + "(())" + "(()(()))"，
删除每个部分中的最外层括号后得到 "()()" + "()" + "()(())" = "()()()()(())"。

示例 3：

txt
输入：s = "()()"
输出：""

解释：
输入字符串为 "()()"，原语化分解得到 "()" + "()"，
删除每个部分中的最外层括号后得到 "" + "" = ""。

提示：

  • 1 <= s.length <= 10^5
  • s[i] 为 '(' 或 ')'
  • s 是一个有效括号字符串

2. 🎯 s.1 - 平衡计数法 ​

js
/**
 * @param {string} s
 * @return {string}
 */
var removeOuterParentheses = function (s) {
  let bal = 0
  let res = ''
  for (const ch of s) {
    if (ch === '(') {
      // 只有当 bal > 0 时，才是内层括号
      if (bal > 0) res += ch
      // 后自增
      bal++
    } else {
      // 先自减
      bal--
      // 只有当 bal > 0 时，才是内层括号
      if (bal > 0) res += ch
    }
  }
  return res
}
  • 时间复杂度：O(n)，其中 n 是字符串的长度，遍历一次字符串
  • 空间复杂度：O(1)，不计输出结果所占空间，只使用了常数级别的额外空间

算法思路：

  • 使用计数器 bal 记录当前括号的嵌套深度，跟踪括号平衡状态
  • 遇到 '(' 时：若 bal > 0（不是最外层左括号），则写入结果；然后 bal++
  • 遇到 ')' 时：先 bal--；若 bal > 0（不是最外层右括号），则写入结果
  • 通过这种方式，每个原语的最外层括号（即 bal 从 0 变为 1 的 '(' 和从 1 变为 0 的 ')'）都不会被写入结果

Discussions